package leetcode_core.leetcode_1;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

public class SuperEggDropByDpTable {

    private Map<String,Integer> memo;
    private StringBuilder stringBuilder;

    private int dp(int k,int n){
        if(k==1){
            return n;
        }
        if(n==0){
            return 0;
        }
        String key =k+","+n;
        if(memo.get(key)!=null){
            return memo.get(key);
        }
        int res = Integer.MAX_VALUE;
        int lo = 1;
        int hi = n;
        while(lo <= hi){
            int mid = (lo+hi)/2;
            int broken = dp(k-1,mid-1);
            int notBroken = dp(k,n-mid);
            if(broken > notBroken){
                hi = mid -1;
                res = Math.min(res,broken+1);
            }else{
                lo = mid +1 ;
                res = Math.min(res,notBroken+1);
            }
        }
        memo.put(key,res);
        return res;
    }

    public int superEggDrop(int K, int N) {
        memo = new HashMap<>();
        return dp(K,N);
    }
    @Test
    public void test(){
        System.out.println(superEggDrop(1,2));
        System.out.println(superEggDrop(2,6));
        System.out.println(superEggDrop(3,14));
    }

}
